Data compression systems are known in the prior art that encode a stream of digital data signals into compressed digital code signals and decode the compressed digital code signals back into the original data. Data compression refers to any process that attempts to convert data in a given format into an alternative format requiring less space than the original. The objective of data compression systems is to effect a savings in the amount of storage required to hold or the amount of time required to transmit a given body of digital information.
To be of practical utility, a general purpose digital data compression system should satisfy certain criteria. The system should have reciprocity. In order for a data compression system to possess the property of reciprocity it must be possible to re-expand or decode the compressed data back into its original form without any alteration or loss of information. The decoded and original data must be identical and indistinguishable with respect to each other. The property of reciprocity is synonymous to that of strict noiselessness used in information theory. Some applications do not require strict adherence to the property of reciprocity. One such application in particular is when dealing with graphical data. Because the human eye is not that sensitive to noise, some alteration or loss of information during the compression de-compression process is acceptable.
The system should provide sufficient performance with respect to the data rates provided by and accepted by the devices with which the data compression and de-compression systems are communicating. The rate at which data can be compressed is determined by the input data processing rate into the compression system, typically in millions of bytes per second (megabytes/sec). Sufficient performance is necessary to maintain the data rates achieved in present day disk, tape and communication systems which rates typically exceed one megabyte/sec. Thus, the data compression and decompression system must have enough data band-widths so as to not adversely affect the overall system. The performance of data compression and de-compression systems is typically limited by the computations necessary to compress and de-compress and the speed of the system components such as, random access memory (RAM), and the like, utilized to store statistical data and guide the compression and de-compression process. Performance for a compression device is characterized by the number of cycles required per input character under the compressor. The fewer the number of cycles, the higher the performance.
Another important criteria in the design of data compression and de-compression systems is compression effectiveness, which is characterized by the compression ratio. The compression ratio is the ratio of data size in uncompressed form divided by the size in compressed form. In order for data to be compressible, the data must contain redundancy. Compression effectiveness is determined by how effectively the compression procedure uses the redundancy in the input data. In typical computer stored data, redundancy occurs both in the nonuniform usage of individual symbology, example digits, bytes, or characters, and in frequent recurrence of symbol sequences, such as common words, blank record fields and the like.
General purpose data compression procedures are known in the prior art, three relevant procedures being the Huffman method, the Tunstall method and the LempeI-Ziv method. The Huffman method is widely known and used, reference thereto in article of D. A. Huffman entitled "A Method For Construction Of Minimum Redundancy Codes", Proceedings IRE, 40, 10 pages 1098-1100 (September, 1952). Reference to the Tunstall algorithm may be found in Doctoral thesis of B. P. Tunstall entitled "Synthesis of Noiseless Compression Codes", Georgia Institute of Technology (September, 1967). Reference may be had to the Lempel-Ziv procedure in a paper authored by J. Ziv and A. Lempel entitled "A Universal Algorithm For Sequential Data Compression", IEEE Transactions on Information Theory, IT-23, 3, pages 337-343 (May, 1977).
One of the first general purpose data compression procedures developed is the Huffman method. Briefly described, the Huffman procedure maps full length segments of symbols into variable length words. The Huffman data compression procedure suffers from two limitations. Firstly, the Huffman procedure operates under the constraint that the input data to be compressed be parsed into fixed length segments of symbols. Although the Huffman procedure provides the best compression ratio that can be obtained under these constraints, when the constraint is relaxed it is possible to obtain significantly better compression ratios by utilizing other procedures. Secondly, Huffman coding requires full knowledge of the statistical characteristic of the source data. The Huffman procedure operates under the assumption that the probability with which each fixed length input segment occurs is known. This requirement of the Huffman procedure can in practice, be satisfied by the use of an adaptive version of the procedure which accumulates the necessary statistics during processing of the data. This, however, is cumbersome, and requires considerable working memory space and performs sub-optimally during adaptation.
The Tunstall algorithm, which maps variable length segments of symbols into fixed length binary words, is complementary to the Huffman procedure with the fixed length constraints now applied to the output segments instead of the input segments. Like the Huffman procedure, the Tunstall procedure requires a foreknowledge of the source data probabilities. Again this foreknowledge requirement can be satisfied to some degree by utilizing an adaptive version that accumulates the statistics during processing of the data.
The Lempel-Ziv procedure maps variable length segments of the symbols into variable length binary words. It is asymptotically optimal when there are no constraints on the input or output segments. In this procedure the input data string is parsed into adaptively grown segments, each segment consisting of an exact copy of an earlier portion of the input string suffixed by one new symbol from the input data. The copy which is to be made is the longest possible and is not constrained to coincide with any earlier parsed segment. The code word which replaces the segment in the output contains information consisting of a pointer to where there earlier copied portion begins, the length of the copy, and the new symbol.
To help keep cost reasonably, data compression is used in the art of page printers such as electrophotography. For example, a 600 dot per inch (DPI) page is about 4 MB in size. By using a compression technique, this can be reduced to about 1 MB. The art of electrophotography printing places a performance constraint for the decompression process. In particular, the compressed data must be decompressed fast enough to provide a constant stream of data to the print engine. To insure that this performance requirement is met, the decompression task is performed by hardware.
Hardware data decompression is typically simplified by first, using a fixed code size and second, reserving special codes that aid the decompressor. By using a fixed code size, the decompressor will accept a fixed code size and produce a fixed code. Thus, for example, a typical hardware decompressor will accept a compressed 8-bit byte and output one or more 8-bit decompressed bytes. Because the input is fixed, special codes are necessary to direct the decompressor. One such arrangement reserves a LITERAL code to indicate that the next code is a literal that is, it is not compressed. Additional, an END_OF_DATA code is defined such that the hardware decompressor stops when it detects the EOD Code.
Because the hardware decompressor simply walks through memory until it detects an EOD code, prior to the present invention, the compressed data must reside in contiguous memory. However, it may not always be possible to find 1 MB of contiguous memory because memory tends to become fragmented over time.